#include <stdio.h>
//队列 （先进先出）
//1️⃣顺序队
//①正常初始化
#define MAXSIZE 100
typedef int ElemType;
typedef struct 
{
    ElemType data[MAXSIZE];
    int front; //队头
    int rear;  //队尾
}Queue;
//初始化
void initqueue(Queue *s)
{
    s->front=0;
    s->rear=0;
}
//入队
int inqueue(Queue *s,ElemType n)
{
    //先判断队列满没满
    if(s->rear>=MAXSIZE)
    {
        if(s->front>0)     //这里是在调整队列，但如果数据很多这样调整效率很低，那有什么好办法吗？
        {                  //可以用循环队列，见下面
            int len=s->front;
            int i;
            for(i=s->front;i<s->rear;i++)
            {
                s->data[i-len]=s->data[i];
            }
            s->front=0;
            s->rear=s->rear-len;
        }
        else
        {
            printf("满了\n");
            return 0;
        }
    }
    s->data[s->rear]=n;   //先插入内容，再++，所以完成入队后rear指向空内容，也就是说rear指向的空间还没存入内容
    s->rear++;
    return 1;
}
//打印
int printqueue(Queue *s)
{
    if(s->rear==0)   //或者if(s->front==s->rear)
    {
        printf("空队\n");
        return 0;
    }
    int i;
    for(i=s->front;i<s->rear;i++)
    {
        printf("%d ",s->data[i]);
    }
    printf("\n");
}
//出队
int outqueue(Queue *s,ElemType *ret)
{
    if(s->rear==0)
    {
        printf("空队\n");
        return 0;
    }
    *ret=s->data[s->front];
    s->front++;
    return 1;
}
int main()
{
    Queue q;
    initqueue(&q);
    //入队
    inqueue(&q,22);
    inqueue(&q,52);
    inqueue(&q,66);
    inqueue(&q,88);
    inqueue(&q,750);
    //打印
    printqueue(&q);
    //出队
    ElemType ret;
    outqueue(&q,&ret);
    printf("出队的数据是%d\n",ret);
    return 0;
}
//②动态内存分配初始化
#include <stdlib.h>
#define MAXSIZE 100
typedef int ElemType;
typedef struct 
{
    ElemType *data;
    int front; //队头
    int rear;  //队尾
}Queue;
//初始化
Queue *initqueue()
{
    Queue *s=(Queue *)malloc(sizeof(Queue));
    s->data=(ElemType *)malloc(sizeof(ElemType)*MAXSIZE);
    s->front=0;
    s->rear=0;
    return s;
}

//2️⃣循环队列
#define MAXSIZE 100
typedef int ElemType;
typedef struct 
{
    ElemType data[MAXSIZE];
    int front; //队头
    int rear;  //队尾
}Queue;
//初始化
void initqueue(Queue *s)
{
    s->front=0;
    s->rear=0;
}
//入队
int inqueue(Queue *s,ElemType n)
{
    if((s->rear+1)%MAXSIZE==s->front)  //这样就抛弃一个空间
    {
        printf("满了\n");
        return 0;
    }
    s->data[s->rear]=n;
    s->rear=(s->rear+1)%MAXSIZE;
    return 1;
}
//打印
int printqueue(Queue *s)
{
    if(s->rear==s->front)  //P79 这里不能写成s->rear==0
    {
        printf("空队\n");
        return 0;
    }
    int i;
    for(i=s->front;i<s->rear;i++)
    {
        printf("%d ",s->data[i]);
    }
}
//出队
int outqueue(Queue *s,ElemType *ret)
{
    if(s->rear==s->front)
    {
        printf("空队\n");
        return 0;
    }
    *ret=s->data[s->front];
    s->front=(s->front+1)%MAXSIZE;
    return 1;
}
int main()
{
    Queue q;
    initqueue(&q);
    //入队
    inqueue(&q,22);
    inqueue(&q,52);
    inqueue(&q,66);
    inqueue(&q,88);
    inqueue(&q,750);
    //打印
    printqueue(&q);
    //出队
    ElemType ret;
    outqueue(&q,&ret);
    printf("出队的数据是%d\n",ret);
    //打印
    printqueue(&q);
    return 0;
}

//3️⃣链队
#include <stdlib.h>
typedef int ElemType;
//头结点的声明
typedef struct queue
{
    ElemType data;
    struct queue *next;
}Queue;
//双指针的声明
typedef struct     //这里可见9.c，涉及到嵌套结构体
{
    Queue *front; //头指针
    Queue *rear;  //尾指针
}Q;
//初始化
Q *initqueue()
{
    Q *q=(Q *)malloc(sizeof(Q));  //给双指针分配内存
    Queue *s=(Queue *)malloc(sizeof(Queue));  //给头节点分配内存
    s->data=0;
    s->next=NULL;
    q->front=s;  //头指针指向头节点
    q->rear=s;   //尾指针指向头节点
    return q;   //返回双指针的地址
}
//入队
void inqueue(Q *s,ElemType n)
{
    //先创建一个新结点
    Queue *q=(Queue *)malloc(sizeof(Queue));  
    q->data=n;
    q->next=NULL;
    s->rear->next=q;
    s->rear=q;
}
//打印
int printqueue(Q *s)
{
    if(s->front->next==NULL)
    {
        printf("空队\n");
        return 0;
    }
    Queue *mid=s->front->next;
    while(mid)
    {
        printf("%d ",mid->data);
        mid=mid->next;
    }
    printf("\n");
    return 1;
}
//出队
int outqueue(Q *s,ElemType *ret)
{
    if(s->front==s->rear)
    {
        printf("空队\n");
        return 0;
    }
    Queue *p=s->front->next;
    *ret=p->data;
    s->front->next=p->next;
    if(p->next==NULL)
    {
        s->rear=s->front;
    }
    free(p);
    return 1;
}
//释放
void freequeue(Q *s)
{
    Queue *p=s->front->next;
    Queue *q;
    while(p)
    {
        q=p->next;
        free(p);
        p=q;
    }
}
int main()
{
    Q *s=initqueue(); 
    //入队：这里看程序员怎么设计，要是用头插法，那尾节点就是队头，首元节点就是队尾
    //要是用尾插法，那首元节点就是队头，尾节点就是队尾
    //这里我们用尾插法
    inqueue(s,22);
    inqueue(s,52);
    inqueue(s,66);
    inqueue(s,88);
    inqueue(s,500);
    //打印
    printqueue(s);
    //出队
    ElemType ret;
    outqueue(s,&ret);
    printf("出队的数据是%d\n",ret);
    //打印
    printqueue(s);
    //释放
    freequeue(s);
    return 0;
}